/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-10-09
 * Time:21:47
 */

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 力扣856:括号的分数
 */

public class scoreOfParentheses {
    public static void main(String[] args) {
        System.out.println(scoreOfParentheses("(())"));
    }

    /**
     * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
     *
     *     () 得 1 分。
     *     AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
     *     (A) 得 2 * A 分，其中 A 是平衡括号字符串。
     */
//    public static int scoreOfParentheses(String s) {
//        int len = s.length();
//        if (len == 2){
//            return 1;
//        }
//        int n = 0;
//        int j = 0;
//        for (int i = 0; i < len; i++) {
//            //当i下标的值是'('时,n++,否则n--即是当i下标的值是')'--
//            if (s.charAt(i) == '('){
//                n++;
//            }else {
//                n--;
//            }
//            if (n == 0){
//                j = i + 1;
//                break;
//            }
//        }
//        //递归实现
//        //当 j == len 时是有包含的情况,因为当 j != len 时j肯定是小于len的
//        if (j == len) {
//            //s.substring(1, len - 1)中的 1 是☞跳过此时字符串的第一个字符直到len - 1
//            return 2 * scoreOfParentheses(s.substring(1, len - 1));
//        } else {
//            return scoreOfParentheses(s.substring(0, j)) + scoreOfParentheses(s.substring(j));
//        }
//    }
    public static int scoreOfParentheses(String s) {
        //队列
        Deque<Integer> deque = new ArrayDeque<>();
        deque.push(0);
        for (int i = 0; i < s.length(); i++) {
            //当对应i下标的字符为'('时 就继续push(0)
            if (s.charAt(i) == '('){
                deque.push(0);
            }else {
                //当遇到')'时
                int n = deque.poll();
                //这里的end计算相当于是计算包含情况的时候
                int end = deque.poll() + Math.max(n * 2,1);
                deque.push(end);
            }
        }
        return deque.pop();
    }
}
